package com.lry.basic.algorithm.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class WaterPuzzle {
    private int A=5;
    private int B=3;
    private int require=2;
    private boolean[] visited = new boolean[A*10+B+1];
    private int[] pre = new int[A*10+B+1];
    private int end = -1;

    private void bfs(){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        visited[0] = true;

        while(!queue.isEmpty()){
            int cur = queue.poll();
            int a = cur/10;
            int b = cur%10;

            List<Integer> nextList = next(a,b);

            for (int next:nextList) {
                if(!visited[next]){
                    queue.offer(next);
                    visited[next] = true;
                    pre[next] = cur;//保存cur到next这条路径
                    if(next/10==require||next%10==require){//找到一个解就提前返回
                        end = next;
                        return;
                    }
                }
            }

        }
    }

    private List<Integer> next(int a,int b){
        //下一个状态的数组
        List<Integer> nextList = new ArrayList<>();
        //经过四种操作的nextList
        //给a装满水
        nextList.add(A*10+b);
        //给b装满水
        nextList.add(a*10+B);
        //a倒掉全部水
        nextList.add(b);
        //b倒掉全部水
        nextList.add(a*10);
        //a倒入b
        int x = Math.min(a,B-b);//看a中的水量和b中剩余的空间，谁小
        nextList.add((a-x)*10+b+x);
        //b倒入a
        int y = Math.min(b,A-a);//看b中的水量和a中剩余的空间，谁小
        nextList.add((a+y)*10+b-y);

        return nextList;
    }

    private Iterable<Integer> path(){
        List<Integer> res = new ArrayList<>();
        if(end==-1){
            return res;
        }
        int cur = end;
        while(cur!=0){
            res.add(0,cur);
            cur = pre[cur];
        }
        res.add(0,0);
        return res;
    }


    public static void main(String[] args) {
        WaterPuzzle puzzle = new WaterPuzzle();
        puzzle.bfs();
        System.out.println(puzzle.path());
    }

}
